Polynomial Modulo Soundness

We want to proof a polynomial modular multiplication (PMM)

$$ A_i(X) ⋅ B_i(X) = R_i(X) \mod P(X) $$

Where $A,B,R$ are low degree.

We can do this using an auxiliary low-degree polynomial $Q_i(X)$ and evaluating the following in a random point $z$

$$ A_i(z) ⋅ B_i(z) = Q_i(z) ⋅ P(z) + R_i(z) $$

To verify many such PMMs we can take a linear combination in a random $α$

$$ \sum_i α^i ⋅ A_i(X) ⋅ B_i(X) = P(z) ⋅ \sum_i α^i ⋅ Q_i(z) + \sum_i α^i ⋅ R_i(z) $$

Question Can the prover pre-sum the quotients? I.e. have an auxiliary low-degree polynomial $Q(X)$ and check:

$$ \sum_i α^i ⋅ A_i(X) ⋅ B_i(X) = P(z) ⋅ Q(z) + \sum_i α^i ⋅ R_i(z) $$

Given $A_i, B_i, R_i, Q$ and $P$ low-degree polynomials that satisfy the above equation. We want to show the only solution is

$$ Q(X) = \sum_i α^i ⋅ Q_i(X) $$

where

$$ Q_i(X) = \frac{A_i(X) ⋅ B_i(X) - R_i(X)}{P(X)} $$

We know that

$$ Q(X) = \frac{\sum_i α^i ⋅ (A_i(X) ⋅ B_i(X) - R_i(X) )}{P(X)} $$

So this amounts to proving

$$ \frac{\sum_i α^i ⋅ (A_i(X) ⋅ B_i(X) - R_i(X) )}{P(X)} = \sum_i α^i ⋅ \frac{A_i(X) ⋅ B_i(X) - R_i(X)}{P(X)} $$

Let's assume that between $A_i(X) ⋅ B_i(X) - R_i(X)$ there are enough degrees of freedom that these can be arbitrary polynomials $D_i(X)$ of degree $2⋅d$:

$$ \frac{\sum_i α^i ⋅ D_i(X)}{P(X)} = \sum_i α^i ⋅ \frac{D_i(X)}{P(X)} $$

Remco Bloemen
Math & Engineering
https://2π.com